package DataStructure.linkList;

/**
 * 160. 相交链表 https://leetcode.cn/problems/intersection-of-two-linked-lists/
 * 题目简述：给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。
 */
public class GetIntersectionNode {

    /**
     * 思路：双指针，p1和p2各自从A、B链表头同时出发，p1遍历完A链表后继续遍历B链表，p2遍历完B链表后继续遍历A链表，
     * 若存在交点则p1和p2会在链表交点处相遇，若不存在交点则最终p1和p2会同时指向null
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        //每次循环中p1和p2都只移动一步
        while(p1 != p2) {
            p1 = p1==null ? headB : p1.next;
            p2 = p2==null ? headA : p2.next;
        }
        //若存在交点则在交点处相遇后退出循环
        //若不存在交点则最终p1和p2也会同时指向null 相等退出循环
        return p1;
    }
}
